home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / Think Class Libraries / COrderedList 2.0 / COrderedList.c next >
Encoding:
C/C++ Source or Header  |  1994-11-30  |  3.9 KB  |  139 lines  |  [TEXT/KAHL]
  1. /******************************************************************************
  2.  COrderedList.c
  3.  
  4.     COrderedList maintains an ordered cluster of objects. It also adds methods
  5.     for iterating over the ordered list.
  6.     
  7.     Copyright (C) 1992 by Brown University. All rights reserved.
  8.  
  9.     Permission is granted to any individual or institution to use, copy,
  10.     or redistribute the binary version of this software and its
  11.     documentation provided this notice and the copyright notices are
  12.     retained.  Permission is granted to any individual or non-profit
  13.     institution to use, copy, modify, or redistribute the source files
  14.     of this software provided this notice and the copyright notices are
  15.     retained.  This software may not be distributed for profit, either
  16.     in original form or in derivative works, nor can the source be
  17.     distributed to other than an individual or a non-profit institution.
  18.     Any  individual or group interested in seeing and/or using these
  19.     source files but who are prevented from doing so by the above
  20.     constraints should contact Don Wolfe, Vice-President for Computer 
  21.     Systems at Brown University, (401) 863-7247, for possible
  22.     software licensing of the source developed at Brown.
  23.  
  24.     Brown University and Andrew James Gilmartin make no representations
  25.     about the suitability of this software for any purpose.
  26.  
  27.      BROWN UNIVERSITY AND ANDREW JAMES GILMARTIN GIVE NO WARRANTY, EITHER
  28.     EXPRESS OR IMPLIED, FOR THE PROGRAM AND/OR DOCUMENTATION PROVIDED,
  29.     INCLUDING, WITHOUT LIMITATION, WARRANTY OF MERCHANTABILITY AND
  30.     WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE.
  31.  
  32.     AUTHOR: Andrew_Gilmartin@Brown.Edu
  33.     MODIFIED: 93-02-04
  34.     
  35. ******************************************************************************/
  36.  
  37. #include "COrderedList.h"
  38.  
  39.  
  40. /******************************************************************************
  41.  IOrderedList
  42.  
  43.     Initialize the list. Note that if no compare function is specified then
  44.     use the defualt.
  45. ******************************************************************************/
  46.  
  47. void COrderedList::IOrderedList( CompareFunc compare )
  48. {
  49.     IUnorderedList( compare );
  50.  
  51. } /* IOrderedList */
  52.  
  53.  
  54.  
  55. /******************************************************************************
  56.  FindIndex
  57.  
  58.     Find the offset of the object in the items list. This method uses bisection
  59.     to narrow down where the object is in the list. If the object is found then
  60.     return TRUE, otherwise return FALSE.
  61. ******************************************************************************/
  62.  
  63. Boolean COrderedList::FindIndex( CObject* anObject, long* foundindex ) 
  64. {
  65.     long left;
  66.     long right;
  67.     long index;
  68.     long relation;
  69.     
  70.     left  = 0;
  71.     right = numItems - 1;
  72.     
  73.     while( left <= right )
  74.     {
  75.         index = ( left + right ) / 2;
  76.  
  77.         relation = (*fCompare)( anObject, (CObject*) (*items)[ index ] );
  78.         
  79.         if ( relation < 0 )
  80.             right = index - 1;
  81.         else if ( relation > 0 )
  82.             left = index + 1;
  83.         else
  84.         {
  85.             *foundindex = index + 1;
  86.             return TRUE;
  87.         }
  88.     }
  89.  
  90.     *foundindex = left + 1;
  91.     return FALSE;
  92.  
  93. } /* FindIndex */
  94.  
  95.  
  96.  
  97. /******************************************************************************
  98.  Add
  99.  
  100.     Add the object to the list in order. Note that this method does not check
  101.     whether the object already exists in the list.
  102. ******************************************************************************/
  103.  
  104. void COrderedList::Add( CObject* anObject )
  105. {
  106.     long index;
  107.  
  108.     FindIndex( anObject, &index );
  109.     InsertAtIndex( &anObject, index );
  110.         
  111. } /* Add */
  112.  
  113.  
  114.  
  115. /******************************************************************************
  116.  Reorder
  117.  
  118.     This method re-sorts the content of the list.
  119. ******************************************************************************/
  120.  
  121. void COrderedList::Reorder( void )
  122. {
  123.     COrderedList* list;
  124.     
  125.     list = (COrderedList*) this->Copy();
  126.     
  127.     this->RemoveAll();
  128.     this->AddAll( list );
  129.  
  130.     list->Dispose();
  131.  
  132.     //         /* An untested alternative.... */
  133.     //
  134.     // HLock( hItems );
  135.     // qsort( *hItems, numItems, elementSize, fCompare );
  136.     // HUnlock( hItems );
  137.  
  138. } /* Reorder */
  139.